package com.milowski.monos.monomial;

import java.io.*;
import java.util.*;
import java.util.logging.*;

/**
 * A monomial tree and its associated algorithms.
 * @author R. Alexander Milowski
 */
public class MonomialTree implements LexOrdered {
   
   static int reduceInterval = 2000;
   static int zeroCountMax = 4;
   static {
      String value = System.getProperty("com.milowski.monos.monomial.MonomialTree.reduceInterval");
      if (value!=null) {
         reduceInterval = Integer.parseInt(value);
      }
      value = System.getProperty("com.milowski.monos.monomial.MonomialTree.zeroCountMax");
      if (value!=null) {
         zeroCountMax = Integer.parseInt(value);
      }
   }
   static protected class EntryPool {
      int chunkSize;
      int reserveSize;
      Entry pool;
      Subtree subtreePool;
      
      class Subtree {
         Entry current;
         Entry sibling;
         Subtree next;
         Subtree(Entry top) {
            current = top;
            sibling = null;
            next = null;
         }
         Subtree(Subtree prev,Entry top) {
            current = top;
            sibling = null;
            next = null;
            prev.next = this;
         }
      }
      
      EntryPool(int initialSize,int chunkSize) {
         this.chunkSize = chunkSize;
         if (chunkSize<=0) {
            throw new RuntimeException("chunk size <= 0 :"+chunkSize);
         }
         Entry last = null;
         pool = null;
         for (int i=0; i<initialSize; i++) {
            last = pool;
            pool = new Entry();
            pool.rightSibling = last;
         }
         reserveSize = initialSize;
         subtreePool = null;
      }

      public Entry get() {
         if (pool==null) {
            if (subtreePool!=null) {
               // Get the current entry from the subtree
               Entry toReturn = subtreePool.current;
               if (toReturn.firstChild==null) {
                  // There is no child, so decide what to do with any
                  // sibling
                  if (toReturn.rightSibling==null) {
                     // There is no sibling, so move to the sibling
                     subtreePool.current = subtreePool.sibling;
                     subtreePool.sibling = null;
                     // Make sure current is non-null
                     if (subtreePool.current==null) {
                        subtreePool = subtreePool.next;
                     }
                  } else {
                     // There is a sibling, so make that current
                     subtreePool.current = toReturn.rightSibling;
                     toReturn.rightSibling = null;
                  }
               } else {
                  // There is a child, so make that current
                  subtreePool.current = toReturn.firstChild;
                  toReturn.firstChild = null;
                  
                  // If we have a right sibling, we'll need to store it.
                  if (toReturn.rightSibling!=null) {
                     if (subtreePool.sibling==null) {
                        // If there isn't a right sibling stored, store it.
                        subtreePool.sibling = toReturn.rightSibling;
                     } else {
                        // Otherwise, append a new subtree
                        Subtree treeCurrent = subtreePool;
                        while (treeCurrent.next!=null) {
                           treeCurrent = treeCurrent.next;
                        }
                        new Subtree(treeCurrent,toReturn.rightSibling);
                     }
                     toReturn.rightSibling = null;
                  }
               }
               return toReturn;
            }
            // TODO: catch memory allocation errors
            Entry last;
            for (int i=0; i<chunkSize; i++) {
               last = pool;
               pool = new Entry();
               pool.rightSibling = last;
            }
            reserveSize += chunkSize;
         }
         reserveSize--;
         
         Entry toReturn = pool;
         pool = toReturn.rightSibling;
         toReturn.firstChild = null;
         toReturn.rightSibling = null;
         return toReturn;
      }
      
      /*
      void putSubtree(Entry e) {
         if (subtreePool==null) {
            subtreePool = new Subtree(e);
         } else {
            Subtree treeCurrent = subtreePool;
            while (treeCurrent.next!=null) {
               treeCurrent = treeCurrent.next;
            }
            new Subtree(treeCurrent,e);
         }
      }*/
      
      public int put(Entry e) {

         int startReserve = reserveSize;

         if (e.firstChild==null) {
            reserveSize++;
            e.rightSibling = pool;
            pool = e;
            return 1;
         }
         Entry current = e.firstChild;
         e.rightSibling = null;
         e.firstChild = null;
         
         while (current!=null) {
            if (current.firstChild!=null) {
               Entry next = current.firstChild;
               current.firstChild = e;
               e = current;
               current = next;
            } else {
               Entry last = current;
               while (last!=null && last.rightSibling!=null && last.rightSibling.firstChild==null) {
                  last = last.rightSibling;
                  reserveSize++;
               }
               Entry next = last.rightSibling;
               last.rightSibling = pool;
               pool = current;
               reserveSize++;
               if (next==null) {
                  current = e;
                  if (current!=null) {
                     e = e.firstChild;
                     current.firstChild = null;
                  }
               } else {
                  current = next;
               }
            }
         }

         /*
         // Return entry
         e.rightSibling = pool;
         pool = e;
         reserveSize++;
         
         // Return all children
         Entry child = e.firstChild;
         while (child!=null) {
            Entry next = child.rightSibling;
            put(child);
            child = next;
         }
         e.firstChild = null;
          */
         
         int diff = reserveSize - startReserve;
         //System.out.println("Returned "+diff);
         return diff;
         
      }
      
      int getPoolSize() {
         return reserveSize;
      }
   }
   
   /**
    * A monomial tree entry.  Each entry represents a
    * variable to a power.
    */
   public static class Entry {
      public short value;
      public Entry rightSibling;
      public Entry firstChild;
      public int leafCount;
      
      Entry() {
         this.rightSibling = null;
         this.firstChild = null;
         this.value = 0;
         this.leafCount = 0;
      }
      
      /**
       * Returns the right sibling of this entry.
       * @return An entry or null for no sibling.
       */
      public Entry getRightSibling() {
         return rightSibling;
      }
      
      public void setRightSibling(Entry r) {
         rightSibling = r;
      }
      
      /**
       * Returns the first child of this entry.
       * @return An entry or null for no child.
       */
      public Entry getFirstChild() {
         return firstChild;
      }
      
      public void setFirstChild(Entry r) {
         firstChild = r;
      }
      
      public int getLeafCount() {
         return leafCount;
      }
      
      public void setLeafCount(int c) {
         leafCount = c;
      }
      
      /**
       * Returns the exponent value.
       */
      public short getValue() {
         return value;
      }
      
      public Entry addChild(Entry child,short childValue) {
         
         // Create a new tree entry for value
         child.value = childValue;
         child.firstChild = null;
         child.rightSibling = null;
         child.leafCount = 1;
         //child.data = null;
         
         if (firstChild==null) {
            // If no children, just assign
            firstChild = child;
         } else {
            
            // Otherwise, add in sorted order
            Entry lastChild = null;
            Entry currentChild = firstChild;
            while (currentChild!=null && currentChild.value<childValue) {
               lastChild = currentChild;
               currentChild = currentChild.rightSibling;
            }
            if (currentChild==null) {
               lastChild.rightSibling = child;
            } else if (currentChild.value==childValue) {
               throw new RuntimeException("Algorithm error: Cannot add child with same value "+childValue);
            } else if (lastChild==null) {
               child.rightSibling = firstChild;
               firstChild = child;
            } else {
               lastChild.rightSibling = child;
               child.rightSibling = currentChild;
            }
         }
         return child;
      }
      
   }
   
   public static class EntryWithData extends Entry {

      public Object data;
      
      public EntryWithData() {
         super();
      }
      
      public EntryWithData(Entry entry,Object data) {
         if (entry!=null) {
            this.rightSibling = entry.rightSibling;
            this.firstChild = entry.firstChild;
            this.value = entry.value;
            this.leafCount = entry.leafCount;
         } else {
            this.rightSibling = null;
            this.firstChild = null;
            this.value = 0;
            this.leafCount = 0;
         }
         this.data = data;
      }
      
      public Object getData() {
         return data;
      }
      
      public void setData(Object data) {
         this.data = data;
      }
   }
   
   public static class TreeIterator implements Iterator {
      
      short [] tempValues;
      protected Entry top;
      protected Entry [] current;
      protected int level;
      protected Entry root;
      protected int width;
      protected boolean started;
      protected boolean finished;
      protected boolean consumed;
      protected boolean returnMonomial;
      
      protected TreeIterator(boolean returnMonomial,int width,Entry root) {
         this.returnMonomial = returnMonomial;
         started = false;
         finished = false;
         consumed = true;
         current = new Entry[width];
         top = root;
         this.width = width;
         this.root = root;
         if (returnMonomial) {
            tempValues = new short[width];
         }
         
      }
      
      public Entry [] current() {
         return current;
      }
      
      public void reset() {
         started = false;
         finished = false;
         consumed = true;
         top = root;
      }
      
      protected void seek() {
         if (finished) {
            return;
         }
         if (!consumed) {
            return;
         }
         if (started) {
            // back to first entry with right sibling
            while (level>=0 && (current[level].rightSibling==null || current[level].rightSibling.firstChild==null)) {
               level--;
            }
            // If level is negative, we're done.
            if (level<0) {
               finished = true;
               return;
            }
         } else {
            started = true;
            level = 0;
            current[level] = root.firstChild;
            // check to see if the tree is empty, then we are done
            if (current[level]==null) {
               finished = true;
               return;
            }
            // initialize to the left subtree
            for (int i=1; i<width; i++) {
               level++;
               // Seek to sibling with child
// TODO: is this necessary?
//               while (current[level-1]!=null && current[level-1].firstChild==null) {
//                  current[level-1] = current[level-1].rightSibling;
//               }
//               if (current[level-1]==null) {
//                  throw new RuntimeException("Algorithm Failure: invalid tree -- not all subtrees are full depth ("+(level-1)+")");
//               }
               current[level] = current[level-1].firstChild;
               if (current[level]==null) {
                  throw new RuntimeException("Algorithm Failure: invalid tree -- not all subtrees are full depth ("+level+")");
               }
            }
            consumed = false;
            return;
         }
         
         // Otherwise, seek to next position
         
         // move to right sibling
         
// TODO: is this necessary?
//         // Seek to right sibling with child
//         while (level>=0 && current[level].rightSibling.firstChild==null) {
//            current[level] = current[level].rightSibling;
//            if (current[level]==null) {
//               level--;
//            }
//         }
         
         // Select the current's right sibling
         current[level] = current[level].rightSibling;
         
         // move to left-most subtree
         int lastLevel = width-1;
         while (level<lastLevel) {
         //for (int i=level+1; i<width; i++) {
            // Seek to sibling with child
            while (current[level]!=null && current[level].firstChild==null) {
               current[level] = current[level].rightSibling;
            }
            if (current[level]==null) {
               do {
                  level--;
                  if (level>=0) {
                     current[level] = current[level].rightSibling;
                  }
               } while (level>=0 && current[level]==null);
               if (level<0) {
                  //throw new RuntimeException("Algorithm Failure: invalid tree -- can't find left subtree of full depth after seeking.");
                  // We weren't able to find a left-most full-depth subtree.  We're done.
                  consumed = true;
                  finished = true;
                  return;
               }
            }
            level++;
            current[level] = current[level-1].firstChild;
            //Logger.getAnonymousLogger().info("Seeking at level "+level);
         }
         //Logger.getAnonymousLogger().info("Seek done.");
         consumed = false;
      }
      
      public boolean hasNext() {
         if (started && !consumed) {
            return !finished;
         }
         if (!finished) {
            seek();
         }
         return !finished;
      }
      
      public Object next() {
         if (!started || consumed) {
            seek();
         }
         if (!finished) {
            consumed = true;
            //return current[level].data==null ? current : current[level].data;
            /*
            if (leafMap!=null) {
               Object data = leafMap.get(current[level]);
               if (data!=null) {
                  return data;
               }
            }*/
            
            if (current[level] instanceof EntryWithData) {
               Object data = ((EntryWithData)current[level]).data;
               if (data!=null) {
                  return data;
               }
            }
            
            if (returnMonomial) {
               for (int i=0; i<current.length; i++) {
                  tempValues[i] = current[i].value;
               }
               return new Monomial(tempValues);
            } else {
               return current;
            }
         } else {
            throw new NoSuchElementException("End of tree reached.");
         }
      }
      
      public void remove() {
         throw new UnsupportedOperationException("Removal not supported by this iteration.");
      }
   }
   
   static class DivisorIterator extends TreeIterator {
      
      short [] values;
      
      DivisorIterator(short [] v,int width,Entry root) {
         super(false,width,root);
         values = v;
      }
      
      protected void seek() {
         // If we're finished, there is nothing to do.
         if (finished) {
            return;
         }
         // If the current position hasn't been consumed, there is nothing to do.
         if (!consumed) {
            return;
         }
         
         // If we've started, we need to find the next left-most matching tree
         if (started) {
            do {
               // back to first entry with right sibling that is less than the value
               while (level>=0 && (current[level].rightSibling==null || current[level].rightSibling.value>values[level])) {
                  level--;
               }
               // If level is negative, we're done.
               if (level<0) {
                  finished = true;
                  return;
               }
               
               // Otherwise, seek to next minimal position
               
               // move to right sibling
               current[level] = current[level].rightSibling;
               
               // move to left-most subtree
               for (int i=level+1; i<width; i++) {
                  level++;
                  current[level] = current[level-1].firstChild;
                  if (current[level].value>values[level]) {
                     level--;
                     break;
                  }
               }
            } while (level!=(width-1));
            consumed = false;
            
         } else {
            
            // otherwise, we need to initialize to the first divisor
            
            started = true;
            level = 0;
            current[level] = root.firstChild;
            // check no first entry or no divisors
            if (current[level]==null || current[level].value>values[level]) {
               finished = true;
               return;
            }
            
            // initialize to the left subtree
            for (int i=1; i<width; i++) {
               level++;
               current[level] = current[level-1].firstChild;
               if (current[level].value>values[level]) {
                  level--;
                  break;
               }
            }
            
            if (level!=(width-1)) {
               // The left-most subtree doesn't divide, so seek to the next position
               seek();
            } else {
               consumed = false;
            }
         }
         
      }
      
   }
   
   protected EntryPool pool;
   protected boolean stop;
   protected Entry root;
   protected int width;
   protected int startSize;
   protected int nodeCount;
   protected Entry [] workTemp;
   protected LexOrder lexorder;
   //protected Map leafMap;
   protected Logger log;
   protected boolean fineLog;
   protected boolean finerLog;
   protected boolean finestLog;
   
   /**
    * Creates a monomial tree using the lexicographic ordering specified.
    * @param order The ordering to use.
    */
   public MonomialTree(LexOrder order) {
      this(order,1024,1024);
   }
   
   /**
    * Creates a monomial tree using the lexicographic ordering specified.
    * @param order The ordering to use.
    * @param initialSize The initial pool size for tree entries.
    * @param chunkSize The increment size for increasing the pool of tree entries.
    */
   public MonomialTree(LexOrder order,int initialSize,int chunkSize) {
      this.log = Logger.getLogger("com.milowski.monos.monomial");
      this.fineLog = log.isLoggable(Level.FINER);
      this.finerLog = log.isLoggable(Level.FINER);
      this.finestLog = log.isLoggable(Level.FINEST);
      this.pool = new EntryPool(initialSize,chunkSize);
      this.root = pool.get();
      this.root.value = (short)-1;
      this.root.leafCount = 0;
      this.nodeCount = 1;
      this.width = order.size();
      this.startSize = pool.getPoolSize();
      this.workTemp = null;
      this.lexorder = order;
      //this.leafMap = null;
   }
   
   /**
    *  Returns the lexicographic ordering associated with this tree.
    */
   public LexOrder getLexOrder() {
      return lexorder;
   }
   
   /**
    * Returns the tree root.  This root does not represent a variable but
    * all of its children represent the first variable in lexicographic order.
    */
   public Entry getRoot() {
      return root;
   }
   
   /**
    * Returns the ideal represented by this monomial tree.
    */
   public MonomialIdeal getIdealGenerator() {
      if (fineLog) {
         log.finer("      ...building new generator for result...");
         
      }
      
      MonomialIdeal result = new MonomialIdeal(lexorder);
      if (root.leafCount==0) {
         return result;
      }
      short [] monomialValues = new short[width];
      buildGenerator(result,0,monomialValues,root.firstChild);
      
      if (fineLog) {
         log.finer("      ...number of monomials: "+result.size());
      }
      return result;
   }
   
   /**
    * Resets the tree and returns all the entries to the pool.
    */
   public void reset() {
      
      //pool.putSubtree(root);
      pool.put(root);
      if (pool.getPoolSize()<startSize) {
         log.severe("      MEMORY LEAK: Tree entries never returned ("+(startSize-pool.getPoolSize())+")");
      }
      root = pool.get();
      root.value = (short)-1;
      root.leafCount = 0;
      nodeCount = 1;
      startSize = pool.getPoolSize();
      
   }
   
   /**
    * Minimmizes the tree by running the Reduce algorithm to remove divided
    * paths.
    * @return The number of entries removed.
    */
   public int minimize() {
      
      if (width<=0) {
         throw new RuntimeException("Depth of tree is not set.");
      }
      if (fineLog) {
         log.finer("         tree has "+nodeCount+" nodes.");
         //log.finer("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory()+", max="+Runtime.getRuntime().maxMemory());
         log.finer("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory());
         //displayTree(top);
         log.finer("      ...reducing tree...");
      }
      
      int startLeafCount = root.leafCount;
      //int removed = reduceNonRecursive(pool,root);
      int removed = reduceRecursive(root,0);
      int removedLeaves = startLeafCount-root.leafCount;
      if (fineLog) {
         log.finer("         removed "+removed+" nodes.");
         log.finer("         removed "+removedLeaves+" leaves.");
      }
      nodeCount -= removed;
      
      return removedLeaves;
   }
   
   /**
    * Indicates whether the tree contains a monomial.
    */
   public boolean contains(Monomial m) {
      return contains(m.getValues());
   }
   
   public boolean contains(short [] values) {
      if (width<=0) {
         throw new RuntimeException("Depth of tree is not set.");
      }
      boolean contained = true;
      Entry current = root.firstChild;
      int level = 0;
      do {
         while (current!=null && current.value<values[level]) {
            current = current.rightSibling;
         }
         if (current==null) {
            contained = false;
         } else if (current.value==values[level]) {
            level++;
            current = current.firstChild;
         } else {
            contained = false;
         }
      } while (contained && level<width);
      
      return contained;
   }
   
   /**
    * Indicates whether the tree divides a monomial.
    */
   public boolean divides(Monomial m) {
      return divides(m.getValues());
   }
   
   public boolean divides(short [] values) {
      if (width<=0) {
         throw new RuntimeException("Depth of tree is not set.");
      }
      int level = 0;
      Entry [] dividedState = new Entry[width];
      boolean divided = false;
      Entry current = root.firstChild;
      while (!divided && current!=null) {
         if (current.value<=values[level]) {
            dividedState[level] = current;
            level++;
            current = current.firstChild;
            if (current==null) {
               divided = true;
            }
         } else {
            current = current.rightSibling;
            while (current==null && level!=0) {
               level--;
               current = dividedState[level].rightSibling;
            }
         }
      }
      
      return divided;
      
   }
   
   /**
    * Iterates all the paths to monomials (leaves) in the tree.
    */
   public TreeIterator iterator() {
      return new TreeIterator(false,width,root);
   }
   
   /**
    * Iterates all the monomials (leaves) in the tree.
    */
   public TreeIterator iterator(boolean returnMonomial) {
      return new TreeIterator(returnMonomial,width,root);
   }
   
   /**
    * Iterates all divisors of a monomial in the tree.
    */
   public Iterator divisors(Monomial m) {
      return new DivisorIterator(m.getValues(),width,root);
   }
   
   public Iterator divisors(short [] m) {
      return new DivisorIterator(m,width,root);
   }
   
   /**
    * Sets the "depth" of the monomial tree to the width of the exponent vector
    * of the monomial argument.
    */
   public void setVariableDepth(Monomial m) {
      setVariableDepth(m.getValues().length);
   }
   
   /**
    * Sets the "depth" of the monomial tree to the specified value.
    */
   public void setVariableDepth(int value) {
      width = value;
   }
   
   /**
    * Adds a monomial to the tree.
    * @param m The monmomial to add.
    */
   public void add(Monomial m) {
      add(m,0,m);
   }
   
   /**
    * Adds a monomial to the tree using an offset for the exponent vector.
    * @param m The monmomial to add.
    * @param offset The offset at which to start in the exponent vector.
    */
   public void add(Monomial m,int offset) {
      add(m,offset,m);
   }
   
   /**
    * Adds a monomial to the tree with associated data.
    * @param m The monmomial to add.
    * @param data The data to associated with the monomial added.
    */
   public void add(Monomial m,Object data) {
      add(m,0,data);
   }
   
   /**
    * Adds a monomial to the tree with associated data.
    * @param m The monmomial to add.
    * @param data The data to associated with the monomial added.
    */
   public void add(short [] values,Object data) {
      if (width<=0) {
         width = values.length;
      }
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      addInternal(false,-1,workTemp,values,0,data);
   }
   
   /**
    * Adds a monomial with associated data to the tree using an offset for the exponent vector.
    * @param m The monmomial to add.
    * @param offset The offset at which to start in the exponent vector.
    * @param data The data to associated with the monomial added.
    */
   public void add(Monomial m,int offset,Object data) {
      if (width<=0) {
         width = m.getValues().length-offset;
      }
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      addInternal(false,-1,workTemp,m.getValues(),offset,data);
   }
   
   boolean addInternal(boolean optimizeLeaf,int dividedDepth, Entry [] dividedState,short [] values,int offset,Object data) {

      /*
      boolean fineLog = log.isLoggable(Level.FINER);
      boolean finestLog = log.isLoggable(Level.FINEST);
       */
      
      // Don't add zero vectors t
      boolean nonzero = false;
      for (int i=0; i<width; i++) {
         if (values[i+offset]>0) {
            nonzero = true;
         }
      }
      if (!nonzero) {
         if (finestLog) {
            StringBuffer msg = new StringBuffer("Ignoring zero monomial: ");
            for (int i=0; i<width; i++) {
               msg.append(" "+values[i+offset]);
            }
            log.finest(msg.toString());
         }
         return false;
      }
      boolean added = false;
      Entry current = root;
      
      for (int i=0; i<width; i++) {
         // Add to the tree
         
         boolean isLeaf = (i+1)==width;
         
         if (isLeaf && optimizeLeaf) {
            // If at the leaf, only keep the lowest value.
            // That is, maintain in a reduced form
            // NOTE: since we keep only one leaf, we don't need to change leafCount
            if (current.firstChild!=null) {
               // Take first and only child and replace value if greater
               Entry leaf = current.firstChild;
               if (leaf.value>values[i+offset]) {
                  // TODO: if we aren't suppose to have disallowed divided monomials,
                  // this check will have reduced the leaves automatically (which isn't what was wanted).
                  leaf.value = values[i+offset];
                  if (data!=null) {
                     /*
                     if (leafMap==null) {
                        leafMap = new HashMap();
                     }
                     leafMap.put(leaf,data);
                      */
                     if (leaf instanceof EntryWithData) {
                        ((EntryWithData)leaf).data = data;
                     } else {
                        EntryWithData newLeaf = new EntryWithData(leaf,data);
                        current.firstChild = newLeaf;
                        pool.put(leaf);
                        leaf = newLeaf;
                     }
                  }
                  //leaf.data = data;
                  if (finestLog) {
                     log.finest(i+": replacing "+values[i+offset]);
                  }
               } else {
                  if (finestLog) {
                     log.finest(i+": ignoring "+values[i+offset]);
                  }
               }
            } else {
               // No children, add leaf
               current = current.addChild(data!=null ? new EntryWithData() : pool.get(),values[i+offset]);
               if (finestLog) {
                  log.finest(i+": adding leaf "+values[i+offset]+", v="+current+", v.right="+current.rightSibling);
               }
               if (data!=null) {
                  /*
                  if (leafMap==null) {
                     leafMap = new HashMap();
                  }
                  leafMap.put(current,data);
                   */
                  ((EntryWithData)current).data = data;
               }
               //current.data = data;
               nodeCount++;
               added = true;
            }
         } else {
            // Search for existing entry at this level
            Entry child = !added && i<=dividedDepth ? dividedState[i] : current.firstChild;
            Entry found = null;
            while (found==null && child!=null) {
               if (finestLog) {
                  log.finest(i+": Checking children item "+child.value+" for "+values[i+offset]);
               }
               if (child.value==values[i+offset]) {
                  found = child;
               }
               child = child.rightSibling;
            }
            
            if (found==null) {
               // Create a new entry
               Entry parent = current;
               current = current.addChild(pool.get(),values[i+offset]);
               if (finestLog) {
                  log.finest(i+": adding "+values[i+offset]+", v="+current+", v.right="+current.rightSibling);
               }
               nodeCount++;
               if (isLeaf && data!=null) {
                  /*
                  if (leafMap==null) {
                     leafMap = new HashMap();
                  }
                  leafMap.put(current,data);
                   */
                  if (current instanceof EntryWithData) {
                     ((EntryWithData)current).data = data;
                  } else {
                     EntryWithData newLeaf = new EntryWithData(current,data);
                     Entry leftSibling = null;
                     Entry currentChild = parent.firstChild;
                     while (currentChild!=current) {
                        leftSibling = currentChild;
                        currentChild = currentChild.rightSibling;
                     }
                     if (leftSibling==null) {
                        parent.firstChild = newLeaf;
                     } else {
                        leftSibling.rightSibling = newLeaf;
                     }
                     pool.put(current);
                     current = newLeaf;
                  }
                  //current.data = data;
               }
               added = true;
               dividedState[i] = current;
               if (i!=0) {
                  // TODO: I don't know if this change will screw up the combine method
                  //if (i<=dividedDepth && dividedState[i-1].firstChild.rightSibling!=null) {
                  if (dividedState[i-1].firstChild.rightSibling!=null) {
                     if (finestLog) {
                        log.finest(i+": incrementing leaf count to top.");
                     }
                     // We've added at least one leaf by adding another child so increment all the way up
                     for (int t=i-1; t>=0; t--) {
                        dividedState[t].leafCount++;
                     }
                     root.leafCount++;
                  }
               } else if (i==0) {
                  root.leafCount++;
               }
            } else {
               Entry parent = current;
               // Otherwise, just traverse level
               if (finestLog) {
                  log.finest(i+": found "+values[i+offset]);
               }
               current = found;
               dividedState[i] = current;
               // TODO: should this replace or leave alone?
               if (isLeaf && data!=null) {
                  /*
                  if (leafMap==null) {
                     leafMap = new HashMap();
                  }
                  leafMap.put(current,data);
                   */
                  if (current instanceof EntryWithData) {
                     ((EntryWithData)current).data = data;
                  } else {
                     EntryWithData newLeaf = new EntryWithData(current,data);
                     Entry leftSibling = null;
                     Entry currentChild = parent.firstChild;
                     while (currentChild!=current) {
                        leftSibling = currentChild;
                        currentChild = currentChild.rightSibling;
                     }
                     if (leftSibling==null) {
                        parent.firstChild = newLeaf;
                     } else {
                        leftSibling.rightSibling = newLeaf;
                     }
                     pool.put(current);
                     current = newLeaf;
                  }
                  //current.data = data;
               }
            }
         }
      }
      return added;
      
   }
   
   /**
    *  Adds a list of monomials to the tree.
    */
   
   public void add(List monomials) {
      if (width<=0 && monomials.size()!=0) {
         width = ((Monomial)monomials.get(0)).getValues().length;
      }
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      Iterator toAdd = monomials.iterator();
      while (toAdd.hasNext()) {
         Monomial m = (Monomial)toAdd.next();
         addInternal(false,-1,workTemp,m.getValues(),0,m);
      }
   }
   
   /**
    * Adds a list of monomials with associated data to the tree.
    */
   public void add(List monomials,Object data) {
      if (width<=0 && monomials.size()!=0) {
         width = ((Monomial)monomials.get(0)).getValues().length;
      }
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      Iterator toAdd = monomials.iterator();
      while (toAdd.hasNext()) {
         Monomial m = (Monomial)toAdd.next();
         addInternal(false,-1,workTemp,m.getValues(),0,data);
      }
   }
   
   /**
    * Combines two monomial lists by their LCM and adds them to the tree.  This is in
    * support of monomial ideal intersections.
    * @param optimizeLeaf A value of 'true' will not allow divided leaves to be added.
    * @param reduce A value of 'true' will run the reduce algorithm to keep the tree minimal.
    * @param checkDivided A value of 'true' will check whether a monomial is divided first before it
    *                     is added.  If it is divided, it will not be added.
    * @param first The first list of monomials.
    * @param second The second list of monomials.
    */
   public void combine(boolean optimizeLeaf,boolean reduce,boolean checkDivided,List first,List second) {
      
      /*
      boolean fineLog = log.isLoggable(Level.FINER);
      boolean finestLog = log.isLoggable(Level.FINEST);
       */
      
      if (width<=0) {
         if (first.size()==0 || second.size()==0) {
            throw new IllegalArgumentException("Both lists of monomials must be non-empty.");
         }
         width = ((Monomial)first.get(0)).getValues().length;
      }
      synchronized (this) {
         stop = false;
      }
      
      long startTime = System.currentTimeMillis();
      
      if (first.size()==0) {
         return;
      }
      
      int checkWidth = ((Monomial)first.get(0)).getValues().length;
      if (checkWidth!=width) {
         throw new RuntimeException("Cannot intersect monomials of different widths.");
      }
      
      if (second!=null) {
         checkWidth = ((Monomial)second.get(0)).getValues().length;
         if (checkWidth!=width) {
            throw new RuntimeException("Cannot intersect monomials of different widths.");
         }
      }
      
      if (fineLog) {
         log.finer("      ...adding to tree:");
         if (second==null) {
            log.finer("         "+first.size()+" monomials");
         } else {
            log.finer("         first has "+first.size()+" monomials");
            log.finer("         second has "+second.size()+" monomials");
         }
      }
      
      Iterator firstMonomials = first.iterator();
      
      short [] intersected = new short[width];
      Entry [] dividedState = new Entry[width];
      
      int monomialCount = 0;
      int dividedCount = 0;
      int containedCount = 0;
      int passCount = 0;
      int zeroCount = 0;
      
      Monomial firstMon = (Monomial)firstMonomials.next();
      short [] fvalues = firstMon.getValues();
      
      Iterator secondMonomials = second==null ? null : second.iterator();
      
      // For each in the first generator
      do {
         
         if (stop) {
            return;
         }
         
         passCount++;
         
         // intersect with the second generator
         if (second==null) {
            System.arraycopy(fvalues, 0, intersected, 0, intersected.length);
            if (firstMonomials.hasNext()) {
               firstMon = (Monomial)firstMonomials.next();
               fvalues = firstMon.getValues();
            }else {
               firstMon = null;
               continue;
            }
         } else {
            short [] svalues;
            if (secondMonomials.hasNext()) {
               Monomial secondMon = (Monomial)secondMonomials.next();
               svalues = secondMon.getValues();
            } else if (firstMonomials.hasNext()) {
               firstMon = (Monomial)firstMonomials.next();
               fvalues = firstMon.getValues();
               secondMonomials = second.iterator();
               continue;
            } else {
               firstMon = null;
               continue;
            }
            
            // Calculate intersected monomial
            for (int i=0; i<width; i++) {
               intersected[i] = fvalues[i]>svalues[i] ? fvalues[i] : svalues[i];
            }
         }
         
         /*
         boolean contained = true;
         Entry current = top.firstChild;
         int level = 0;
         do {
            while (current!=null && current.value<intersected[level]) {
               current = current.rightSibling;
            }
            if (current==null) {
               contained = false;
            } else if (current.value==intersected[level]) {
               level++;
               current = current.firstChild;
            } else {
               contained = false;
            }
         } while (contained && level<width);
          
         if (contained) {
            if (verbose) {
               log.print("Contained ");
               for (int i=0; i<intersected.length; i++) {
                  log.print(" "+intersected[i]);
               }
               log.println();
            }
            containedCount++;
            continue;
         }
          */
         
         int level = 0;
         boolean divided = false;
         int dividedDepth = -1;
         Entry current = root.firstChild;
         while (!divided && current!=null) {
            if (current.value<=intersected[level]) {
               dividedState[level] = current;
               dividedDepth = level;
               level++;
               current = current.firstChild;
               if (current==null) {
                  divided = true;
               }
            } else {
               current = current.rightSibling;
               while (current==null && level!=0) {
                  level--;
                  current = dividedState[level].rightSibling;
               }
            }
         }
         
         
         //boolean divided = dividedRecursive(0,intersected,top.firstChild);
         //boolean divided = dividedQueued(0,intersected,top);
         
         if (divided) {
            if (finestLog) {
               StringBuffer msg = new StringBuffer("Divided ");
               for (int i=0; i<intersected.length; i++) {
                  msg.append(" "+intersected[i]);
               }
               log.finest(msg.toString());
            }
            dividedCount++;
            continue;
         }
         
         monomialCount++;
         
         if (finestLog) {
            StringBuffer formatted = new StringBuffer();
            for (int i=0; i<intersected.length; i++) {
               formatted.append(' ');
               formatted.append(Short.toString(intersected[i]));
            }
            log.finest("Adding monomial "+formatted.toString());
         }
         boolean added = addInternal(optimizeLeaf,dividedDepth,dividedState,intersected,0,null);
         
         if (reduce && (monomialCount%reduceInterval)==0) {
            
            if (zeroCount<zeroCountMax) {
               if (fineLog) {
                  log.finer("         tree has "+nodeCount+" nodes.");
                  //log.println("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory()+", max="+Runtime.getRuntime().maxMemory());
                  log.finer("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory());
                  //displayTree(top);
                  log.finer("      ...reducing tree...");
               }
               
               int startLeafCount = root.leafCount;
               
               //int removed = reduce(pool,verbose ? "" : null,minusOne,top);
               //int removed = reduceNonRecursive(pool,root);
               int removed = reduceRecursive(root,0);
               if (fineLog) {
                  log.finer("         removed "+removed+" nodes.");
                  log.finer("         removed "+(startLeafCount-root.leafCount)+" leaves.");
               }
               if (removed==0) {
                  zeroCount++;
               } else {
                  zeroCount = 0;
               }
               nodeCount -= removed;
            } else {
               if (fineLog) {
                  log.finer("         skipping reduce.");
                  log.finer("         tree has "+nodeCount+" nodes.");
               }
            }
            
         }
         
         
      } while (firstMon!=null);
      
      // Now we've got the intersection as a sorted tree
      
      if (fineLog) {
         log.finer("      Considered "+(monomialCount+containedCount+dividedCount)+", contained="+containedCount+", divided="+dividedCount);
         log.finer("         tree has "+nodeCount+" nodes.");
         log.finer("         tree has "+root.leafCount+" leaves.");
         //log.println("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory()+", max="+Runtime.getRuntime().maxMemory());
         log.finer("         Memory: total="+Runtime.getRuntime().totalMemory()+", free="+Runtime.getRuntime().freeMemory());
         //displayTree(top);
      }
      
      if (reduce) {
         if (fineLog) {
            log.finer("      ...reducing tree...");
         }
         int startLeafCount = root.leafCount;
         // Reduce the intersection
         //int removed = reduce(pool,verbose ? "" : null,minusOne,top);
         //int removed = reduceNonRecursive(pool,root);
         int removed = reduceRecursive(root,0);
         
         nodeCount -= removed;
         
         if (fineLog) {
            log.finer("         removed "+removed+" nodes");
            log.finer("         removed "+(startLeafCount-root.leafCount)+" leaves.");
         }
      }
      
      if (fineLog) {
         log.finer("      Elapsed Time : "+(System.currentTimeMillis()-startTime));
      }
   }
   
   private int reduceRecursive(Entry parent,int level) {
      int change = 0;
      //boolean finest = log.isLoggable(Level.FINEST);
      if (finestLog) {
         log.finest(level+": Reducing subtree at value "+parent.value);
      }
      
      int nextLevel = level+1;
      
      if (parent.firstChild!=null) {
         // Check children first
         
         Entry child = parent.firstChild;
         Entry lastChild = null;
         while (child!=null) {
            int removed = reduceRecursive(child,nextLevel);
            if (removed>0) {
               change += removed;
            }
            lastChild = child;
            child = child.rightSibling;
         }
         
         // Check siblings
         Entry sibling = parent.rightSibling;
         Entry lastSibling = parent;
         while (sibling!=null) {
            int removed = reduceSibling(parent,sibling,level);
            if (removed>0) {
               change += removed;
               if (sibling.firstChild==null) {
                  if (finestLog) {
                     log.finest(level+": Removing non-leaf "+sibling.value+" with no children.");
                  }
                  lastSibling.rightSibling = sibling.rightSibling;
                  pool.put(sibling);
                  change++;
                  sibling = lastSibling.rightSibling;
               } else {
                  lastSibling = sibling;
                  sibling = sibling.rightSibling;
               }
            } else {
               lastSibling = sibling;
               sibling = sibling.rightSibling;
            }
         }
      } else {
         // This is a leaf, so just keep the lowest
         Entry sibling = parent.rightSibling;
         while (sibling!=null) {
            if (finestLog) {
               log.finest(level+": Removing leaf "+sibling.value+" divided by sibling.");
            }
            Entry toReturn = sibling;
            sibling = sibling.rightSibling;
            pool.put(toReturn);
            change++;
         }
         parent.rightSibling = null;
      }
      return change;
      
   }
   
   public int reduceSibling(Entry divisor, Entry sibling, int level) {
      //boolean finest = log.isLoggable(Level.FINEST);
      if (finestLog) {
         log.finest(level+": Comparing divisor "+divisor.value+" to sibling "+sibling.value);
      }
      int change = 0;
      int nextLevel = level+1;
      Entry divisorChild = divisor.firstChild;
      while (divisorChild!=null) {
         Entry siblingChild = sibling.firstChild;
         Entry lastSiblingChild = null;
         
         // Seek until the divisor is less than the sibling
         while (siblingChild!=null && divisorChild.value>siblingChild.value) {
            lastSiblingChild = siblingChild;
            siblingChild = siblingChild.rightSibling;
         }
         
         // Process all the siblings that are greater
         while (siblingChild!=null) {
            if (finestLog) {
               log.finest(nextLevel+": divisor "+divisorChild.value+" <= "+siblingChild.value+", checking subtree.");
            }
            if (siblingChild.firstChild==null) {
               // We're at a leaf, so the sibling is divided
               if (finestLog) {
                  log.finest(nextLevel+": sibling is leaf & divided, removing leaf and right siblings");
               }
               // Remove the current sibling child and all its right siblings
               //boolean removeMap = leafMap!=null;
               while (siblingChild!=null) {
                  Entry toReturn = siblingChild;
                  siblingChild = siblingChild.rightSibling;
                  //if (removeMap) {
                  //   leafMap.remove(toReturn);
                  //}
                  pool.put(toReturn);
                  change++;
               }
               // Fix the previous sibling child if there is one.
               if (lastSiblingChild!=null) {
                  lastSiblingChild.rightSibling = null;
               } else {
                  sibling.firstChild = null;
               }
            } else {
               int removed = reduceSibling(divisorChild,siblingChild,nextLevel);
               if (removed>0) {
                  change += removed;
                  if (siblingChild.firstChild==null) {
                     if (finestLog) {
                        log.finest(nextLevel+": Removing non-leaf "+siblingChild.value+" with no children.");
                     }
                     if (lastSiblingChild==null) {
                        sibling.firstChild = siblingChild.rightSibling;
                        pool.put(siblingChild);
                        change++;
                        siblingChild = sibling.firstChild;
                     } else {
                        lastSiblingChild.rightSibling = siblingChild.rightSibling;
                        pool.put(siblingChild);
                        change++;
                        siblingChild = lastSiblingChild.rightSibling;
                     }
                  } else {
                     lastSiblingChild = siblingChild;
                     siblingChild = siblingChild.rightSibling;
                  }
               } else {
                  lastSiblingChild = siblingChild;
                  siblingChild = siblingChild.rightSibling;
               }
            }
         }
         divisorChild = divisorChild.rightSibling;
      }
      
      return change;
   }
   
   static final Byte CHECK_CHILDREN = new Byte((byte)0);
   static final Byte CHECK_SIBLINGS = new Byte((byte)1);
   static final Byte DONE = new Byte((byte)2);
   
   private int reduceNonRecursive(EntryPool pool,Entry top) {
      
      /*
      boolean fineLog = log.isLoggable(Level.FINER);
      boolean finestLog = log.isLoggable(Level.FINEST);
       */
      
      int removed = 0;
      int depth = 0;
      if (finestLog) {
         log.finest("width="+width);
      }
      // Special case this trivial case so we don't have to mess this up
      if (width==1) {
         Entry toReturn = top.firstChild.rightSibling;
         top.firstChild.rightSibling = null;
         if (toReturn!=null) {
            Entry next;
            do {
               next = toReturn.rightSibling;
               removed += pool.put(toReturn);
               toReturn = next;
            } while (next!=null);
         }
         return removed;
      }
      
      Entry [] path = new Entry[width];
      Entry [] siblings = new Entry[width];
      List ancestors = new ArrayList();
      Entry tchild = top.firstChild;
      ancestors.add(CHECK_CHILDREN);
      ancestors.add(tchild);
      do {
         Entry current = (Entry)ancestors.remove(ancestors.size()-1);
         path[depth] = current;
         Object state = ancestors.remove(ancestors.size()-1);
         if (state==CHECK_CHILDREN) {
            if (finestLog) {
               log.finest("depth="+depth+", queue size="+ancestors.size()+", value="+current.value+", leafCount="+current.leafCount+", checking children...");
            }
            // Store the current vertex in the next state (check siblings)
            ancestors.add(CHECK_SIBLINGS);
            ancestors.add(current);
            
            // We must have more than one leaf to have siblings in the subtree to check
            if (current.leafCount>1) {
               
               // We queue all the children in the initial state
               Entry child = current.firstChild;
               // Non-leaves have children to check first
               if (child.firstChild!=null) {
                  // Push the child on in the correct order
                  int numberChildren = 0;
                  while (child!=null) {
                     if (finestLog) {
                        log.finest("child at item "+numberChildren+" value "+child.value+" with leafCount="+child.leafCount);
                     }
                     if (numberChildren==0) {
                        ancestors.add(CHECK_CHILDREN);
                        ancestors.add(child);
                     } else {
                        int pos = ancestors.size()-(2*numberChildren);
                        ancestors.add(pos,child);
                        ancestors.add(pos,CHECK_CHILDREN);
                     }
                     child = child.rightSibling;
                     numberChildren++;
                  }
                  if (finestLog) {
                     log.finest("Added "+numberChildren+" children to the queue.");
                  }
                  depth++;
               } else {
                  // We have a non-optimized tree will multiple leaves with the same parent
                  // This is easy.  Just drop the siblings
                  if (finestLog) {
                     log.finest("Severing non-optimized leaf sibliings.");
                  }
                  Entry toReturn = child.rightSibling;
                  child.rightSibling = null;
                  current.leafCount = 1;
                  if (toReturn==null) {
                     throw new RuntimeException("Bad monomial tree: leave has no sibling but parent leaf count > 1");
                  }
                  do {
                     Entry next = toReturn.rightSibling;
                     removed += pool.put(toReturn);
                     toReturn = next;
                     if (toReturn!=null && toReturn.firstChild!=null) {
                        throw new RuntimeException("Bad monomial tree: sibling identified as leaf but there are children--not all paths has the same depth.");
                     }
                  } while (toReturn!=null);
               }
            }
         } else if (state==CHECK_SIBLINGS) {
            if (finestLog) {
               StringBuffer msg = new StringBuffer("At ");
               for (int i=0; i<=depth; i++) {
                  msg.append(" "+path[i].value);
               }
               log.finest(msg.toString());
               log.finest("depth="+depth+", queue size="+ancestors.size()+", checking siblings...");
               log.finest("last="+path[depth]+", last.right="+path[depth].rightSibling);
            }
            for (int i=0; i<depth; i++) {
               siblings[i] = path[i];
            }
            Entry sibling = current.rightSibling;
            while (sibling!=null) {
               int compareDepth = depth+1;
               /*
               if (log!=null) {
                  log.println("width="+width+",depth="+depth+",compareDepth="+compareDepth);
                  log.flush();
               }
                */
               siblings[depth] = sibling;
               boolean siblingMoved = false;
               path[compareDepth] = current.firstChild;
               siblings[compareDepth] = sibling.firstChild;
               /*
               if (log!=null) {
                  log.println("path["+depth+"]="+path[depth].value);
                  log.println("path["+compareDepth+"]="+path[compareDepth].value);
               }
               for (int i=0; i<=compareDepth; i++) {
                  if (siblings[i]==null) {
                     if (log!=null) {
                        log.println("depth="+depth+",compareDepth="+compareDepth);
                        for (int j=0; j<i; j++) {
                           log.print(" "+path[j].value);
                        }
                        log.println();
                        for (int j=0; j<i; j++) {
                           log.print(" "+siblings[j].value);
                        }
                        log.println();
                        log.flush();
                     }
                     throw new RuntimeException("Algorithm Failure: sibling at "+i+" is null.");
                  }
               }
                */
               do {
                  if (finestLog) {
                     StringBuffer msg = new StringBuffer("At ");
                     for (int i=0; i<=compareDepth; i++) {
                        msg.append(" "+path[i].value);
                     }
                     log.finest(msg.toString());
                     msg = new StringBuffer("vs ");
                     for (int i=0; i<=compareDepth; i++) {
                        if (i<depth) {
                           msg.append(" "+path[i].value);
                        } else {
                           msg.append(" "+siblings[i].value);
                        }
                     }
                     log.finest(msg.toString());
                     log.finest("depth="+depth+", compareDepth="+compareDepth +", path="+path[compareDepth]+", sibling="+siblings[compareDepth]);
                     log.finest("sibling.right="+siblings[compareDepth].rightSibling);
                  }
                  if (path[compareDepth].value<=siblings[compareDepth].value) {
                     if (siblings[compareDepth].firstChild==null) {
                        // We're reached a leaf and so this sibling is divided.
                        int severDepth = compareDepth;
                        while (severDepth>0 && siblings[severDepth].rightSibling==null && siblings[severDepth-1].firstChild==siblings[severDepth]) {
                           severDepth--;
                        }
                        if (finestLog) {
                           log.finest("severing, severDepth="+severDepth);
                        }
                        if (severDepth==0) {
                           
                           // sever the whole right subtree
                           
                           if (finestLog) {
                              log.finest("Severing right subtree from root.");
                           }
                           
                           Entry leftSibling = top.firstChild;
                           while (leftSibling.rightSibling!=siblings[severDepth]) {
                              leftSibling = leftSibling.rightSibling;
                           }
                           if (leftSibling==siblings[severDepth]) {
                              throw new RuntimeException("Algorithm failure: right subtree should not be the only child of the root.");
                           }
                           leftSibling.rightSibling = siblings[severDepth].rightSibling;
                           if (finestLog) {
                              log.finest("  sibling="+sibling);
                              log.finest("  leftSibling="+leftSibling+", leftSibling.rightSibling="+siblings[severDepth].rightSibling);
                           }
                           top.leafCount--;
                           
                           // We'll need to remove the sibling from the ancestors queue as well
                           int pos;
                           while ((pos=ancestors.indexOf(siblings[severDepth]))>=0) {
                              ancestors.remove(pos);
                              ancestors.remove(pos-1);
                           }
                           
                           // We are putting back the sibling, so we need to move it for the iteration
                           sibling = sibling.rightSibling;
                           siblingMoved = true;
                           
                           // Return the severed subtree
                           removed += pool.put(siblings[severDepth]);
                           
                           // break out of the loop as we've severed the sibling
                           compareDepth = severDepth;
                           
                        } else {
                           Entry parent = siblings[severDepth-1];
                           if (parent.firstChild==siblings[severDepth]) {
                              if (finestLog) {
                                 log.finest("Severing from parent "+parent+" first child "+parent.firstChild+" replacing with "+parent.firstChild.rightSibling);
                                 log.finest("New right sibling "+parent.firstChild.rightSibling.rightSibling);
                              }
                              parent.firstChild = parent.firstChild.rightSibling;
                           } else {
                              Entry leftSibling = parent.firstChild;
                              while (leftSibling.rightSibling!=siblings[severDepth]) {
                                 leftSibling = leftSibling.rightSibling;
                              }
                              leftSibling.rightSibling = siblings[severDepth].rightSibling;
                              if (finestLog) {
                                 log.finest("Severing from parent "+parent+" child "+siblings[severDepth]+" from left sibling "+leftSibling);
                              }
                           }
                           
                           // fix the leaf count
                           for (int i=severDepth-1; i>=0; i--) {
                              siblings[i].leafCount--;
                           }
                           top.leafCount--;
                           
                           if (severDepth>depth) {
                              // we've severed a sub-tree and so we need to check siblings at that level
                              if (finestLog) {
                                 log.finest("Checking sibling of severed subtree...");
                              }
                              
                              Entry toReturn = siblings[severDepth];
                              
                              if (siblings[severDepth].rightSibling!=null) {
                                 siblings[severDepth] = siblings[severDepth].rightSibling;
                              } else {
                                 severDepth--;
                              }
                              
                              // Return the severed subtree
                              removed += pool.put(toReturn);
                              
                              compareDepth = severDepth;
                           } else {
                              if (finestLog) {
                                 log.finest("Breaking as subtree was rooted at sibling...");
                              }
                              
                              // break out of the loop as we've severed the sibling
                              compareDepth = depth;
                              
                              // We'll need to remove the sibling from the ancestors queue as well
                              int pos;
                              while ((pos=ancestors.indexOf(siblings[severDepth]))>=0) {
                                 ancestors.remove(pos);
                                 ancestors.remove(pos-1);
                              }
                              
                              // We are putting back the sibling, so we need to move it for the iteration
                              sibling = sibling.rightSibling;
                              siblingMoved = true;
                              
                              // Return the severed subtree
                              removed += pool.put(siblings[severDepth]);
                              
                           }
                        }
                     } else {
                        compareDepth++;
                        path[compareDepth] = path[compareDepth-1].firstChild;
                        siblings[compareDepth] = siblings[compareDepth-1].firstChild;
                     }
                  } else {
                     
                     // check for alternate paths down compare path
                     int pathDepth = compareDepth;
                     while (pathDepth>0 && pathDepth>depth && path[pathDepth].rightSibling==null) {
                        pathDepth--;
                     }
                     // check for alternate paths down the siblings
                     int siblingsDepth = compareDepth;
                     while (siblingsDepth>0 && siblingsDepth>depth && siblings[siblingsDepth].rightSibling==null) {
                        siblingsDepth--;
                     }
                     
                     if (finestLog) {
                        log.finest("compareDepth="+compareDepth+", next sibling depth="+siblingsDepth+", next path depth="+pathDepth);
                     }
                     
                     if (siblingsDepth>pathDepth) {
                        // sibling depth is deepest
                        
                        compareDepth = siblingsDepth;
                        if (compareDepth>depth) {
                           // move to the next sibling subtree
                           if (finestLog) {
                              log.finest("Moving to "+siblings[compareDepth].rightSibling+" from "+siblings[compareDepth]+" at depth "+compareDepth);
                           }
                           siblings[compareDepth] = siblings[compareDepth].rightSibling;
                           
                           // reset the paths to the left most subtree
                           int nextDepth = compareDepth;
                           while (nextDepth<width) {
                              path[nextDepth] = path[nextDepth-1].firstChild;
                              nextDepth++;
                           }
                        }
                        // otherwise, compareDepth<=depth breaks the loop
                        
                     } else {
                        // path depth is deepest
                        compareDepth = pathDepth;
                        if (compareDepth>depth) {
                           // move to the next path subtree
                           if (finestLog) {
                              log.finest("Moving to path "+path[compareDepth].rightSibling+" from "+path[compareDepth]+" at depth "+compareDepth);
                           }
                           path[compareDepth] = path[compareDepth].rightSibling;
                        }
                        // otherwise, compareDepth<=depth breaks the loop
                     }
                     
                  }
                  
               } while (compareDepth>depth);
               
               if (finestLog) {
                  log.finest("Moving to next sibling: ");
               }
               if (!siblingMoved) {
                  sibling = sibling.rightSibling;
               }
               if (sibling!=null) {
                  log.finest(sibling.toString());
               }
            }
            if (ancestors.size()!=0) {
               Entry next = (Entry)ancestors.get(ancestors.size()-1);
               if (current.rightSibling!=next) {
                  depth--;
               }
            }
         }
         if (ancestors.size()==0 && tchild.rightSibling!=null) {
            depth = 0;
            tchild = tchild.rightSibling;
            ancestors.add(CHECK_CHILDREN);
            ancestors.add(tchild);
         }
      } while (ancestors.size()!=0);
      
      return removed;
   }
   
   /**
    * Removes the divisors from the tree.
    * @return The number of entries removed.
    */
   public int removeDivisors() {
      int originalSize = pool.reserveSize;
      removeDivisors(root,0);
      return pool.reserveSize - originalSize;
   }
   
   private void removeDivisors(Entry parent,int level) {
      if (finerLog) {
         log.finer(level+": checking value "+parent.value);
      }
      int nextLevel = level+1;
      Entry current = parent.firstChild;
      Entry last = null;
      do {
         if (current.firstChild!=null) {
            // Check the subtree first
            removeDivisors(current,nextLevel);
         }
         Entry sibling = current.rightSibling;
         boolean moved = false;
         while (sibling!=null) {
            if (current.firstChild==null) {
               if (finerLog) {
                  log.finer(nextLevel+": at leaf, keeping only largest leaf.");
               }
               // we're at a leaf.  Keep the largest leaf.
               Entry lastLeaf = current;
               while (lastLeaf.rightSibling!=null) {
                  if (finerLog) {
                     log.finer(nextLevel+": Dropping value "+lastLeaf.value);
                  }
                  Entry toReturn = lastLeaf;
                  lastLeaf = lastLeaf.rightSibling;
                  pool.put(toReturn);
               }
               parent.firstChild = lastLeaf;
               current = lastLeaf;
               if (finerLog) {
                  log.finer(nextLevel+": Keeping "+lastLeaf.value);
               }
            } else {
               int oldCount = current.leafCount;
               if (dividesSibling(nextLevel,current,sibling)) {
                  // we've removed divisor children of current, so
                  // fix leaf count and check to see if we remove current
                  current.leafCount -= (oldCount-current.leafCount);
                  if (current.firstChild==null) {
                     Entry toReturn = current;
                     current = current.rightSibling;
                     pool.put(toReturn);
                     if (last==null) {
                        parent.firstChild = current;
                     } else {
                        last.rightSibling = current;
                     }
                     moved = true;
                     break;
                  }
               }
            }
            sibling = sibling.rightSibling;
         }
         if (!moved) {
            last = current;
            current = current.rightSibling;
         }
      } while (current!=null);
   }
   
   private boolean dividesSibling(int level,Entry current,Entry sibling) {
      if (finerLog) {
         log.finer(level+": Comparing siblings "+current.value+" to "+sibling.value);
      }
      int nextLevel = level+1;
      Entry currentChild = current.firstChild;
      Entry lastCurrent = null;
      boolean divisorFound = false;
      while (currentChild!=null) {
         boolean moved = false;
         Entry siblingChild = sibling.firstChild;
         short currentValue = currentChild.value;
         while (siblingChild!=null && currentChild.value>siblingChild.value) {
            if (finerLog) {
               log.finer(nextLevel+": skipping sibling "+siblingChild.value+" as not divided by "+currentChild.value);
            }
            siblingChild = siblingChild.rightSibling;
         }
         while (!moved && siblingChild!=null && currentChild.value<=siblingChild.value) {
            // We're dividing
            if (currentChild.firstChild==null) {
               if (finerLog) {
                  log.finer(nextLevel+": Leaf reached, so sibling divided.");
                  log.finer(nextLevel+": Removing divisor leaf "+currentChild.value);
               }
               // these are leaves, so the current can be removed
               current.leafCount--;
               divisorFound = true;
               moved = true;
               if (lastCurrent==null) {
                  current.firstChild = currentChild.rightSibling;
                  pool.put(currentChild);
                  currentChild = current.firstChild;
               } else {
                  lastCurrent.rightSibling = currentChild.rightSibling;
                  Entry toReturn = currentChild;
                  currentChild = lastCurrent;
                  pool.put(currentChild);
               }
            } else {
               if (finerLog) {
                  log.finer(nextLevel+": Checking subtree as divisor "+currentChild.value+" divides sibling "+siblingChild.value);
               }
               // Check the subtree
               int oldCount = currentChild.leafCount;
               if (dividesSibling(nextLevel,currentChild,siblingChild)) {
                  divisorFound = true;
                  current.leafCount -= (oldCount-currentChild.leafCount);
                  if (currentChild.firstChild==null) {
                     if (finerLog) {
                        log.finer(nextLevel+": Removing "+currentChild.value+" as there are no children.");
                     }
                     Entry toReturn = currentChild;
                     currentChild = currentChild.rightSibling;
                     if (lastCurrent==null) {
                        current.firstChild = currentChild;
                     } else {
                        lastCurrent.rightSibling = currentChild;
                     }
                     pool.put(toReturn);
                     moved = true;
                     break;
                  }
               }
            }
            siblingChild = siblingChild.rightSibling;
            if (finerLog && siblingChild!=null) {
               log.finer(nextLevel+": Moving to next sibling "+siblingChild.value);
            }
         }
         if (finerLog && !moved && siblingChild!=null) {
            log.finer(nextLevel+": Non-dividing sibling value "+siblingChild.value+" for divisor child "+currentValue);
         }
         if (!moved && currentChild!=null) {
            lastCurrent = currentChild;
            currentChild = currentChild.rightSibling;
            if (finerLog && currentChild!=null) {
               log.finer(nextLevel+": Moving to next divisor "+currentChild.value);
            }
         }
      }
      return divisorFound;
      
   }
   
   private void buildGenerator(LexOrderedList gen,int level,short [] monomialValues,Entry child) {
      while (child!=null) {
         monomialValues[level] = child.value;
         if (level<(monomialValues.length-1)) {
            buildGenerator(gen,level+1,monomialValues,child.firstChild);
         } else {
            gen.add(new Monomial(monomialValues));
         }
         child = child.rightSibling;
      }
   }
   
   /**
    * Interrupts the current method (if possible).  This allows long-running
    * intersections to be interrupted.
    */
   public void interrupt() {
      synchronized (this) {
         stop = true;
      }
   }
   
   /**
    * Projects the tree by removing the first variable and merging subtrees.
    */
   public void project() {
      if (width==1) {
         throw new RuntimeException("Cannot project past one variable.");
      }
      if (root.firstChild!=null) {
         Entry current = root.firstChild;
         Entry newRoot = pool.get();
         newRoot.value = -1;
         do {

            if (newRoot.firstChild==null) {
               newRoot.firstChild = current.firstChild;
            } else {
               Entry position = newRoot.firstChild;
               Entry child = current.firstChild;
               while (child!=null) {
                  while (position.rightSibling!=null && position.value<child.value) {
                     position = position.rightSibling;
                  }
                  if (position.value==child.value) {
                     // ther're equal so we need to merge subtrees
                     merge(1,position,child);
                     Entry toReturn = child;
                     child = child.rightSibling;
                     pool.put(toReturn);
                  } else if (position.rightSibling!=null) {
                     // right sibling is greater but position is less
                     Entry toInsert = child;
                     child = child.rightSibling;
                     toInsert.rightSibling = position.rightSibling;
                     position.rightSibling = toInsert;
                  } else if (position.value<child.value) {
                     // No right sibling and all are less than current
                     // They're order is OK
                     position.rightSibling = child;
                     // And we're done
                     child = null;
                  } else if (position.value>child.value) {
                     // No right sibling but greater value can only happen if there is one child
                     newRoot.firstChild = child;
                     child = child.rightSibling;
                     newRoot.firstChild.rightSibling = position;
                  }
               }
            }

            //Severe and save
            current.firstChild = null;
            Entry putBack = current;

            // move to the next sibling
            current = current.rightSibling;

            // put it back
            pool.put(putBack);
         } while (current!=null);

         //assign the new root and put back the old
         root.firstChild = null;
         pool.put(root);
         root = newRoot;
      }
      width--;
      LexOrder newOrder = new LexOrder();
      for (int i=1; i<lexorder.size(); i++) {
         newOrder.add(lexorder.get(i));
      }
      lexorder = newOrder;
      minimize();
   }
   
   /**
    * Produces a string format of the tree (very large).
    */
   public String toString() {
      StringBuffer sb = new StringBuffer();
      debugFormat(sb,"",root);
      return sb.toString();
   }
   
   public String toString(LexOrder inScopeOrder) {
      return toString();
   }
   
   void debugFormat(StringBuffer sb,String prefix,Entry parent) {
      boolean inline = parent.leafCount==1;
      if (!inline) {
         sb.append(prefix);
      }
      sb.append("( ");
      sb.append(Short.toString(parent.value));
      Entry child = parent.firstChild;
      if (child!=null) {
         String newPrefix = prefix + " ";
         if (!inline) {
            sb.append("\n");
            sb.append(newPrefix);
            sb.append("[ ");
         } else {
            sb.append(" [ ");
         }
         if (!inline) {
            sb.append("\n");
         }
         while (child!=null) {
            debugFormat(sb,newPrefix,child);
            child = child.rightSibling;
            if (child!=null) {
               sb.append(inline ? ", " : ",\n");
            }
         }
         if (!inline) {
            sb.append(newPrefix);
         }
         sb.append("] ");
         if (!inline) {
            sb.append("\n");
            sb.append(prefix);
         }
      }
      sb.append(")");
      if (!inline) {
         sb.append("\n");
      }
   }
   
   /**
    * Removes the maximal artinian powers from the tree.
    * @param maximal An array of maximal powers in lexicographic order.
    */
   public void removeMaximal(short []maximal) {
      removeMaximal(root,-1,maximal);
   }
   
   private void removeMaximal(Entry parent,int level,short [] maximal) {
      int nextLevel = level+1;
      Entry child = parent.firstChild;
      Entry last = null;
      while (child.rightSibling!=null) {
         if (child.firstChild!=null) {
            removeMaximal(child,nextLevel,maximal);
         }
         last = child;
         child = child.rightSibling;
      }
      if (child.firstChild!=null) {
         removeMaximal(child,nextLevel,maximal);
      }
      if (child.value==maximal[nextLevel]) {
         child.value = 0;
         if (parent.firstChild!=child) {
            // we only need to change things when there is more than one child
            if (parent.firstChild.value==0) {
               if (last!=null) {
                  last.rightSibling = null;
               }
               if (child.firstChild!=null) {
                  // we need to merge nodes
                  // NOTE: the level is one-based for 'merge'
                  merge(nextLevel+1,parent.firstChild,child);
                  pool.put(child);
               } else {
                  // drop the unnecessary leaf
                  pool.put(child);
               }
            } else {
               // shuffle the child to the front
               if (last!=null) {
                  last.rightSibling = null;
               }
               child.rightSibling = parent.firstChild;
               parent.firstChild = child;
            }
         }
      }
   }
   
   /**
    * Adjust the tree and reverse the deformation caused by making an ideal
    * generic.
    * @param powerAdjustments The adjustments made to the ideal to make it generic.
    */
   public void adjust(IdealGenerator.Adjustment [][] powerAdjustments) {
      if (finerLog) {
         log.finer("Using adjustments: ");
         for (int i=0; i<powerAdjustments.length; i++) {
            StringBuffer sb = new StringBuffer();
            sb.append(i+": ");
            for (int j=0; j<powerAdjustments[i].length; j++) {
               if (powerAdjustments[i][j]!=null) {
                  sb.append(powerAdjustments[i][j].from+":"+powerAdjustments[i][j].to);
                  sb.append(' ');
               }
            }
            log.finer(sb.toString());
         }
      }
      if (finestLog) {
         log.finest(this.toString());
      }
      adjustSubtree(root,powerAdjustments,0);
      if (finestLog) {
         log.finest(this.toString());
      }
      mergeDuplicates(root,0);
   }
   
   private void adjustSubtree(Entry parent,IdealGenerator.Adjustment [][]powerAdjustments,int level) {
      if ((level+1)>width) {
         throw new RuntimeException("Bad level "+level+", can't be more than "+(width-1));
      }
      // Start with the first child
      Entry current = parent.firstChild;
      Entry last = null;
      
      if (finerLog) {
         log.finer("Adjusting level "+level);
      }
      
      // Adjust all the children of the parent
      do {
         if (finerLog) {
            log.finer(level+": Checking value "+current.value);
         }
         
         int i;
         // Iterate this level and adjust as needed.
         for (i=0; i<powerAdjustments[level].length && powerAdjustments[level][i]!=null && current.value>powerAdjustments[level][i].to; i++);
         if (i<powerAdjustments[level].length && powerAdjustments[level][i]!=null && current.value==powerAdjustments[level][i].to) {
            current.value = powerAdjustments[level][i].from;
            if (finerLog) {
               log.finer(level+": Changed to "+current.value);
            }
         }
         
         // Adjust children first
         if (current.firstChild!=null) {
            // Process subtree
            int oldCount = current.leafCount;
            adjustSubtree(current,powerAdjustments,level+1);
            parent.leafCount += current.leafCount - oldCount;
         }
         
         boolean moved = false;
         /*
         // Check for duplicates
         if (last!=null && last.value==current.value) {
            // We've got a duplicate, so we need to merge subtrees
            if (last.firstChild==null) {
               // This is a leaf, so just drop the duplicate
               if (log.isLoggable(Level.FINE)) {
                  log.fine(level+": Dropping duplicate leaf for value "+last.value);
               }
               last.rightSibling = current.rightSibling;
               Entry toReturn = current;
               current = last;
               if (current==parent.firstChild) {
                  last = null;
               }
               pool.put(toReturn);
               parent.leafCount--;
               if (parent.leafCount==0) {
                  throw new RuntimeException("Algorithm failure: parent has no children!");
               }
               if (log.isLoggable(Level.FINE)) {
                  log.fine(level+": Leaf count: "+parent.leafCount);
               }
            } else {
               if (log.isLoggable(Level.FINE)) {
                  log.fine(level+": Merging subtrees for value "+last.value);
               }
               int oldCount = last.leafCount;
               merge(level,last,current);
               parent.leafCount += last.leafCount - oldCount;
               last.rightSibling = current.rightSibling;
               Entry toReturn = current;
               current = current.rightSibling;
               pool.put(current);
               moved = true;
            }
         }
          */
         
         if (!moved) {
            // Move forward
            last = current;
            current = current.rightSibling;
         }
         
      } while (current!=null);
   }
   
   private void mergeDuplicates(Entry parent,int level) {
      
      if (finerLog) {
         log.finer(level+": Checking subtrees...");
      }
      // Simply the subtrees first
      int nextLevel = level+1;
      Entry current = parent.firstChild;
      if (parent.firstChild.firstChild!=null) {
         current = parent.firstChild;
         while (current!=null) {
            mergeDuplicates(current,nextLevel);
            current = current.rightSibling;
         }
      }
      
      // Now check this level
      current = parent.firstChild;
      Entry last = null;
      do {
         boolean moved = false;
         boolean isLeaf = current.firstChild==null;
         if (last!=null) {
            if (current.value==last.value) {
               if (finerLog) {
                  log.finer(nextLevel+": merging for value "+current.value+", current="+current);
               }
               if (!isLeaf) {
                  merge(nextLevel,last,current);
               }
               last.rightSibling = current.rightSibling;
               Entry toReturn = current;
               current = current.rightSibling;
               pool.put(toReturn);
               moved = true;
            }
         }
         if (!moved) {
            last = current;
            current = current.rightSibling;
         }
      } while (current!=null);
   }
   
   private int depthOf(Entry parent) {
      return parent.firstChild==null ? 1 : depthOf(parent.firstChild)+1;
   }
   private boolean checkForDepth(Entry parent,int depth) {
      if (parent.firstChild==null) {
         return depth==1;
      } else {
         Entry child = parent.firstChild;
         int nextDepth = depth-1;
         while (child!=null) {
            if (!checkForDepth(child,nextDepth)) {
               return false;
            }
            child = child.rightSibling;
         }
         return true;
      }
   }
   
   private void merge(int level,Entry target,Entry from) {
      // This is a distructive merge.
      // Only the 'from' is not manipulated except to sever its children
      
      // We're processing the next level down
      int nextLevel = level+1;
      
      /*
      int topTargetDepth = depthOf(target);
      int topFromDepth = depthOf(from);
      if (!checkForDepth(target,width-level+1)) {
         //StringBuffer sb = new StringBuffer();
         //debugFormat(sb,"",target);
         //log.fine(sb.toString());
         throw new RuntimeException("Bad tree: target is not consistently of depth "+(width-level+1));
      }
      if (!checkForDepth(from,width-level+1)) {
         //StringBuffer sb = new StringBuffer();
         //debugFormat(sb,"",from);
         //log.fine(sb.toString());
         throw new RuntimeException("Bad tree: from is not consistently of depth "+(width-level+1)+", left most="+topFromDepth);
      }
      if (topTargetDepth!=topFromDepth) {
         throw new RuntimeException("Algorithm failure: unbalanced depths, target="+topTargetDepth+", from="+topFromDepth);
      }
       **/
      
      // Start with the first child
      Entry fromChild = from.firstChild;
      
      // Merge all the children of the from node
      do {
         Entry targetChild = target.firstChild;
         Entry targetLastChild = null;
         boolean foundSpot = false;
         do {
            // Stop if greater or equal
            if (finerLog) {
               log.finer(nextLevel+": "+targetChild.value+">="+fromChild.value+" ?");
            }
            if (targetChild.value>=fromChild.value) {
               foundSpot = true;
            } else {
               
               // Move forward
               targetLastChild = targetChild;
               targetChild = targetChild.rightSibling;
            }
            
         } while (targetChild!=null && !foundSpot);
         Entry next = fromChild.rightSibling;
         if (foundSpot) {
            if (finerLog) {
               log.finer(nextLevel+": Merging nodes for values: targetChild="+targetChild.value+", fromChild="+fromChild.value);
            }
            // We've found an insertion spot
            // Check to see if it is the same value
            if (targetChild.value==fromChild.value) {
               // merge if there are children
               if (fromChild.firstChild!=null) {
                  if (finerLog) {
                     log.finer(nextLevel+": Merging subtrees");
                  }
                  /*
                  int targetDepth = depthOf(targetChild);
                  int fromDepth = depthOf(fromChild);
                  if (targetDepth!=fromDepth) {
                     throw new RuntimeException("Algorithm failure: unbalanced depths, target="+targetDepth+", from="+fromDepth);
                  }
                   */
                  if (targetChild.firstChild==null) {
                     throw new RuntimeException("Algorithm failure: targetCurrent should have child, tree not balanced (level="+nextLevel+")!");
                  }
                  int oldCount = targetChild.leafCount;
                  merge(nextLevel,targetChild,fromChild);
                  target.leafCount += targetChild.leafCount - oldCount;
                  pool.put(fromChild);
               } else {
                  if (finerLog) {
                     log.finer("Dropping leaf.");
                  }
                  pool.put(fromChild);
               }
            } else  {
               if (finerLog) {
                  log.finer(nextLevel+": Inserting subtree before "+targetChild.value+", targetLastChild="+targetLastChild);
               }
               /*
               int targetDepth = depthOf(targetChild);
               int fromDepth = depthOf(fromChild);
               if (targetDepth!=fromDepth) {
                  throw new RuntimeException("Algorithm failure: unbalanced depths, target="+targetDepth+", from="+fromDepth);
               }
                */
               // we can just insert the whole tree
               fromChild.rightSibling = targetChild;
               if (targetLastChild==null) {
                  target.firstChild = fromChild;
               } else {
                  targetLastChild.rightSibling = fromChild;
               }
               target.leafCount += fromChild.leafCount;
            }
         } else {
            if (finerLog) {
               log.finer(nextLevel+": Appending subtree and siblings: target="+targetLastChild.value+", current="+fromChild.value);
            }
            // The whole tree and its siblings get added to the right
            targetLastChild.rightSibling = fromChild;
            while (fromChild!=null) {
               target.leafCount += fromChild.leafCount;
               fromChild = fromChild.rightSibling;
            }
            next = null;
         }
         
         // Move forward
         fromChild = next;
      } while (fromChild!=null);
      from.firstChild = null;
   }
   
}
